課程名稱 |
演算法 Algorithms |
開課學期 |
110-2 |
授課對象 |
電機資訊學院 電機工程學系 |
授課教師 |
江蕙如 |
課號 |
EE4033 |
課程識別碼 |
901 39000 |
班次 |
|
學分 |
3.0 |
全/半年 |
半年 |
必/選修 |
必修 |
上課時間 |
星期四2,3,4(9:10~12:10) |
上課地點 |
博理112 |
備註 |
外系學生加選請於加退選時向授課老師詢問。 限本系所學生(含輔系、雙修生) 總人數上限:80人 |
|
|
課程簡介影片 |
|
核心能力關聯 |
核心能力與課程規劃關聯圖 |
課程大綱
|
為確保您我的權利,請尊重智慧財產權及不得非法影印
|
課程概述 |
The study of algorithms is at the heart of computer science. This course focuses on fundamental results in this area, including the unifying principles and underlying concepts of algorithm design and analysis.
We expect everyone to be comfortable reading, even writing, proofs. Several programming assignments will be given to embody the ideas. Moreover, we hope that everyone can learn general problem-solving techniques. |
課程目標 |
1. Study unifying principles and concepts of algorithm design and analysis
2. Polish your critical thinking and problem-solving technique |
課程要求 |
Prerequisite: two out of the following four courses
1. Data structures
2. Discrete mathematics
3. Computer programming in C
4. Computer programming in C++
*** C/C++ programming skill is a must *** |
預期每週課後學習時數 |
|
Office Hours |
每週三 12:30~13:00 備註: by appointment |
指定閱讀 |
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 3rd Ed., McGraw Hill/MIT Press, 2009 (CLRS) |
參考書目 |
Recommended books on algorithms:
1. J. Kleinberg and E. Tardos, Algorithm Design, Addison Wesley, 2006
(Cornell)
2. S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani, Algorithms, McGraw-
Hill, 2007 (UC Berkeley)
Recommended books on graph theory:
1. Douglas B. West, Introduction to Graph Theory, 2nd Edition, Pearson, 2000.
2. 演算法觀點的圖論 (Graph Theory, with an Algorithmic Perspective)作者:張鎮華 |
評量方式 (僅供參考) |
No. |
項目 |
百分比 |
說明 |
1. |
Final |
30% |
|
2. |
Midterm |
20% |
|
3. |
Three programming assignments |
25% |
|
4. |
Four in-class quizzes |
5% |
|
5. |
DIY |
2% |
|
6. |
Four homework assignments |
18% |
|
7. |
Bonus |
0% |
Up to 2%
Class participations, Q&A, extra DIY, etc. |
|
週次 |
日期 |
單元主題 |
第1週 |
|
Foundations: Ch1, Ch2, Ch3 |
第2週 |
|
Foundations (Divide-and-Conquer): Ch2.3, Ch4 |
第3週 |
|
Sorting: Ch6, Ch7 |
第4週 |
|
Sorting: Ch8, Ch9
Quiz#1 |
第5週 |
|
Trees: Ch12
RB Trees: Ch13 (offline) |
第6週 |
|
Advanced Design (Dynamic Programming): Ch15 |
第7週 |
|
Advanced Design (Dynamic Programming): Ch15 |
第8週 |
|
Advanced Design (Greedy Algorithms): Ch16
Quiz#2 |
第9週 |
|
Midterm Exam 9:20-12:10 |
第10週 |
|
Amortized Analysis: Ch17 (offline)
Graphs BFS/DFS: Ch22 |
第11週 |
|
Graphs MST: Ch23
Disjoint Set: Ch21 |
第12週 |
|
Graphs SSSP: Ch24
Quiz#3 |
第13週 |
|
Graphs APSP: Ch25 |
第14週 |
|
Graphs Flow: Ch26 |
第15週 |
|
NP-completeness: Ch34, 35.1~35.2
|
第16週 |
|
Review
Quiz#4 |
第17週 |
|
Final Exam 9:20-12:10 |
第18週 |
|
Optional for advanced topics |
|